/*
 * Since we need to print linked list reversely, we could use
 * a stack and push each node, from head to tail, to the stack.
 * When all nodes are pushed into stack, we pop them to print 
 *
 */
class ReverseLinkedList{
	private Stack<Integer> stack;
	public ReverseLinkedList(){
		stack = new Stack<Integer>();
	}
	
	public void printReverseStack(Node head){
		if(head == null) return;
		
		while(head != null){ // push node to stack
			stack.push(head.getData());
			head = head.getNext();
		}
		
		int value = 0;
		while(!stack.isEmpty()){
			value = stack.pop();
			System.out.print(value+" ");
		}
	}
	
	/* Assume Node has two attributes: data and next, 
	 * data is the int value and next points 
	 * to its next node. The time complexity is O(n)
	 */
	public void printReverseRecur(Node head){
		if(head != null) {                     
			printReverseRecur(head.next);		  // recursion
			System.out.print(" " + head.data);
			return;
		}		
	}

// Another approach could be use a stack and push each node, from head to tail, to the stack.
// When all nodes are pushed into stack, we pop them to print
// The time complexity is also O(n) but it use less space because of not using recursion

/* 
 * Node Class
 */
class Node{
	private int data;
	Node next = null;
	
	public Node(int d){ // Constructor
		data = d;
	}
	public int getData(){ // getter method for node data
		return data;
	}
	
	public void setNext(int d){ // pointer to the next node
		Node n = new Node(d);
		next = n;
	}
}